package leetcode_题库;

import java.util.*;

/**
 * Created by IntelliJ IDEA.
 *
 * @ProjectName leetcode
 * @Author Ding
 * @CreateTime 2022/8/24 15:25 星期三
 */
public class _542_01矩阵 {

    private static int min;

    public static void main(String[] args) {
        int[][] mat = new int[][]{
                {0, 0, 1, 0, 1, 1, 1, 0, 1, 1},
                {1, 1, 1, 1, 0, 1, 1, 1, 1, 1},
                {1, 1, 1, 1, 1, 0, 0, 0, 1, 1},
                {1, 0, 1, 0, 1, 1, 1, 0, 1, 1},
                {0, 0, 1, 1, 1, 0, 1, 1, 1, 1},
                {1, 0, 1, 1, 1, 1, 1, 1, 1, 1},
                {1, 1, 1, 1, 0, 1, 0, 1, 0, 1},
                {0, 1, 0, 0, 0, 1, 0, 0, 1, 1},
                {1, 1, 1, 0, 1, 1, 0, 1, 0, 1},
                {1, 0, 1, 1, 1, 0, 1, 1, 1, 0},
        };
        System.err.println(Arrays.deepToString(updateMatrix(mat)));
    }

    public static int[][] updateMatrix(int[][] mat) {
        //标记数组
        boolean[][] through = new boolean[mat.length][mat[0].length];
        //遍历
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[0].length; j++) {
                if (mat[i][j] != 1) {
                    continue;
                }
                //最小值初始化为最大值
                min = Integer.MAX_VALUE;
                //深度优先，传入步长为默认0，和标记数组
                dfs(mat, i, j, 0, through);
                mat[i][j] = min;
            }
        }
        return mat;
    }

    /**
     *
     * 递归必然超时
     *
     * > 2022/08/26 19:05:38
     * 测试用例:[[0,0,1,0,1,1,1,0,1,1],[1,1,1,1,0,1,1,1,1,1],[1,1,1,1,1,0,0,0,1,1],[1,0,1,0,1,1,1,0,1,1],[0,0,1,1,1,0,1,1,1,1],[1,0,1,1,1,1,1,1,1,1],[1,1,1,1,0,1,0,1,0,1],[0,1,0,0,0,1,0,0,1,1],[1,1,1,0,1,1,0,1,0,1],[1,0,1,1,1,0,1,1,1,0]]
     * 期望结果:[[0,0,1,0,1,2,1,0,1,2],[1,1,2,1,0,1,1,1,2,3],[2,1,2,1,1,0,0,0,1,2],[1,0,1,0,1,1,1,0,1,2],[0,0,1,1,1,0,1,1,2,3],[1,0,1,2,1,1,1,2,1,2],[1,1,1,1,0,1,0,1,0,1],[0,1,0,0,0,1,0,0,1,2],[1,1,1,0,1,1,0,1,0,1],[1,0,1,1,1,0,1,2,1,0]]
     * stdout:
     *
     * @param mat
     * @param i
     * @param j
     * @param through
     * @return
     */
    private static void dfs(int[][] mat, int i, int j, int cnt, boolean[][] through) {
        //超出边界，或走过这个点了，返回MAX_VALUE
        if (i < 0 || j < 0 || i >= mat.length || j >= mat[0].length || through[i][j]) {
            return;
        }
        if (mat[i][j] == 0) {
            min = Math.min(min,cnt);
            return;
        }

        through[i][j] = true;

        dfs(mat, i - 1, j, cnt + 1, through);
        dfs(mat, i + 1, j, cnt + 1, through);
        dfs(mat, i, j - 1, cnt + 1, through);
        dfs(mat, i, j + 1, cnt + 1, through);
        //回溯
        through[i][j] = false;
    }

}
